package com.yang.Tree;

/*
二分搜索树
*/

import javax.swing.tree.TreeNode;
import java.util.*;

// 二分搜索树内的元素必须具有可比性
public class BST {
    public static void main(String[] args) {
        SolutionBST solutionBST = new SolutionBST();
        solutionBST.add(2);
        solutionBST.add(1);
        solutionBST.add(3);
    }
}

class SolutionBST <E extends Comparable<E>>{
    private class Node{
        // 1.能够存放任何类的元素
        public E e;
        // 2.拥有左右两个孩子节点
        public Node left, right;

        // 二叉搜索树节点构造函数
        public Node(E e){
            this.e = e;
            left = null;
            right = null;
        }
    }
    // 成员变量 1.根节点 2.记录成员数
    private Node root;
    private int size;

    // 二叉搜索树根节点构造函数
    public SolutionBST(){
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public Boolean isEmpty(){
        return size == 0;
    }

    public void add(E e){
        root = add(root, e);
    }

    private Node add(Node node, E e){
        if ( node == null){
            size++;
            return new Node(e);
        }

        if(e.compareTo(node.e) < 0){
            node.left = add(node.left, e);
        }
        else if(e.compareTo(node.e) > 0){
            node.right = add(node.right, e);
        }
        // 返回根节点(保证根节点还是原来的根节点)
        return node;
    }

    // 不用递归添加节点的方法
    private Node addNoRe(Node node, E e){
        if(node == null){
            root = new Node(e);
        }
        while (node != null){
            if(e.compareTo(node.e) < 0 && node.left == null){
                node.left = new Node(e);
                return root;
            }
            else if(e.compareTo(node.e) > 0 && node.right == null){
                node.right = new Node(e);
                return root;
            }
            if(e.compareTo(node.e) < 0 ){
                node = node.left;
            }
            else if(e.compareTo(node.e) > 0 ){
                node = node.right;
            }
        }
        return root;
    }

    // 查询元素是否存在于树
    public boolean contains(E e){
        return contains(root, e);
    }
    private boolean contains(Node node, E e){
        if(node == null){
            return false;
        }
        if (e.compareTo(node.e) == 0){
            return true;
        }
        else if (e.compareTo(node.e) < 0){
            return contains(node.left, e);
        }
        //  否则就是 (e.compareTo(node.e) > 0)
        else {
            return contains(node.right, e);
        }
    }

    // choice 1为非递归方式
    public void preOrder(List<E> result, Integer choice){
//        preOrder(root);
        if(choice == 1){
            preOrderNoRecursion(root, result);
        }else{
            preOrder(root);
        }
    }

    // 前序遍历 先访问根节点的递归方法
    private void preOrder(Node node){
        if (node == null){
            return;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

    public List preOrderNoRecursion(Node node, List<E> result){
        if(node == null){
            return result;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while ( !stack.isEmpty() ){
            Node tempNode = stack.pop();
            result.add(tempNode.e);
            if (tempNode.right != null){
                stack.push(tempNode.right);
            }
            if (tempNode.left != null){
                stack.push(tempNode.left);
            }
        }
        return result;
    }

    // 中序遍历，先访问左子树再访问该节点 然后访问该节点的 右子树

    public void inOrder(){
        inOrder(root);
    }

    // 中序遍历 先访问左节点的递归方法
    private void inOrder(Node node){
        if (node == null){
            return;
        }
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    // 后序遍历，先访问左子树再访问该节点 然后访问该节点的 右子树

    public void postOrder(){
        postOrder(root);
    }

    // 后序遍历 先访问左节点的递归方法
    // 应用，比如需要手动释放内存，那么就需要先释放孩子节点后释放父节点
    private void postOrder(Node node){
        if (node == null){
            return;
        }
        postOrder(node.right);
        postOrder(node.left);
        System.out.println(node.e);
    }

    // 层序遍历
    public void levelOrder(){
        Queue<Node> queue = new LinkedList<>();
        // 创建队列的同时先把根节点放进去
        queue.add(root);
        while( !queue.isEmpty() ){
            // 1.根据层序遍历定义，首先先访问根节点
            Node cur = queue.remove();
            System.out.println(cur.e);

            if (cur.left != null){
                queue.add(cur.left);
            }
            if (cur.right != null){
                queue.add(cur.right);
            }
        }
    }

/*  public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        checkFunDfs(root, 0);
        return result;
    }
    // 递归方式层序遍历
        public void checkFunDfs(TreeNode node, Integer deep){
        if(node == node){
            return;
        }

        deep++;

        if(result.size() < deep){
            List<Integer> item = new ArrayList<Integer>();
            result.add(item);
        }
        result.get(deep-1).add(node.val);

        checkFunDfs(node.left, deep);
        checkFunDfs(node.right, deep);
        }

        */
    // 寻找二叉搜索树中的最小值和最大值
    public E minNum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is Empty");
        }
        return minNum(root).e;
    }
    // 返回最小值所在的节点
    private Node minNum(Node node){
        if(node.left == null){
            return node;
        }
        return minNum(node.left);
    }
    public E maxNum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is Empty");
        }
        return maxNum(root).e;
    }
    // 返回最小值所在的节点
    private Node maxNum(Node node){
        if(node.right == null){
            return node;
        }
        return maxNum(node.right);
    }

    // 找到了最大最小值，那么如何进行删除？
    // 如果是叶子节点那么直接删除即可，但是如果是根节点，他是有左右孩子的，这个时候只需要让根节点的父节点指向它的左孩子或者右孩子
    public E removeMin(){
        E res = maxNum();
        root = removeMin(root);
        return res;
    }

    // 删除掉最大节点也是如此道理
    // 删除掉以node节点为根的二分搜索树的最小节点
    // 并返回删除节点后的新的二分搜索树节点
    private Node removeMin(Node node){
        // 如果该节点的左节点为空，说明是最小节点
        if(node.left == null){
            // 那么就新建一个节点类型 承接这个节点的右孩子，该节点将是新的节点(替代被删除的节点)
            // 如果被删除节点的右孩子为空也无所谓，因为空的右节点依然为空
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }
        // 本来的最小左节点被删除了,所以现在需要把新的最小子节点返回给根节点(如果该最小左节点存在右孩子，那么这个节点就是右孩子)
        node.left = removeMin(node.left);
        // 移除改根节点的最小节点后 该根节点肯定是没有改变的
        return node;
    }

    // 对于移除任意元素  如果移除的元素只有左孩子或者右孩子那就直接让它的左孩子或右孩子代替它的位置
    // 但是如果它左右孩子都有的话怎么办？
    // 这个时候我们选择 它的后继节点的条件是，离他最近的节点 就是比它大，但是是比它大的数中最小的数 就是右孩子中最小的数（前驱也可以就是左子树中的最大值）
    // 找到这个数并删除掉它
    public void remove(E e){
        root = remove(root, e);
    }

    private Node remove(Node node, E e){
        if(node == null){
            return null;
        }

        if(e.compareTo(node.e) < 0){
            node.left = remove(node.left, e);
            return node;
        }else if(e.compareTo(node.e) > 0){
            node.right = remove(node.right, e);
            return node;
        }
        // 找到了目标e
        else {
            // 待删除节点左子树为空
            if (node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }
            // 待删除节点右子树为空
            if (node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }
            // 上面都不满足 这里就是左右孩子都存在的情况
            // 找到比待删除节点大的最小节点 就是右孩子的最后一个左孩子
            //  用这个节点代替待删除节点
            //
            Node successor = minNum(node.right);
            // 返回移除掉最小节点的右节点
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;

            return successor;
        }
    }

// 翻转二叉树
// DFS todo 有空把BFS也写了
        public Node invertTree(Node root) {
            if( root == null ){
                return root;
            }
            invertTree(root.left);
            invertTree(root.right);
            swap(root);
            return root;
        }

        public void swap(Node root){
            Node node;
            node = root.left;
            root.left = root.right;
            root.right = node;
        }

    /*
    * 判断是否为对称二叉树
    * todo 尝试用递归的方式完成
    * */
    public boolean isSymmetric(Node root) {
        // 判空
        if(root == null){
            return true;
        }
        Deque<Node> queue = new LinkedList<>();
        // 关键点就是塞进去分别塞入左右子树  判断左子树的左孩子是否和 右子树的右孩子相等
        // 即外侧的节点是否相等，内侧的节点是否相等？
        queue.add(root.left);
        queue.add(root.right);
        while( !queue.isEmpty() ){
            Node outside = queue.poll();
            Node inside = queue.poll();
            // 如果队列不为空遇到 相等的null 则跳过本次循环
            if( outside == null && inside == null){
                continue;
            }else if( (outside == null && inside != null) || (outside != null && inside == null) || (outside.e != inside.e)){
                return false;
            }
            queue.add(outside.left);
            queue.add(inside.right);
            queue.add(outside.right);
            queue.add(inside.left);
        }
        return true;
    }
// 递归实现求最大深度
    public int maxDepthDFS(Node root) {
        if(root == null){
            return 0;
        }
        int leftDeep = maxDepthDFS(root.left);
        int rightDeep = maxDepthDFS(root.right);
        // 返回每个节点的深度 + 1 因为要算上本层中间
        return Math.max(rightDeep, leftDeep) + 1;
    }

    public int maxDepthBFS(Node root) {
        int maxDeep = 0;
        if(root == null){
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while( !queue.isEmpty()){
            int size = queue.size();
            maxDeep ++;
            for(int i=0; i < size; i++){
                Node node = queue.poll();
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }

        }
        return maxDeep;
    }

// todo  N叉树深度
//    public int maxDepth(Node root) {
//        if(root == null){
//            return 0;
//        }
//        int deep = 0;
//        // 如果它的孩子节点不为空,那么就依次取出来进行递归
//        if(root.children != null){
//            for(Node child : root.children){
//                deep = Math.max(maxDepth(child), deep);
//            }
//        }
//        return deep + 1;
//    }


    // 求最小深度
    public int minDepth(Node root) {
        return getMinDepth(root);
    }
    public int getMinDepth(Node node){
        if (node == null){
            return 0;
        }
        int leftDepth = getMinDepth(node.left);
        int rightDepth = getMinDepth(node.right);

        // 注意这里是甄别叶子结点和父节点的地方
        // 叶子节点就是没有孩子节点  而不单单是node=null的节点
        // 有的节点存在左孩子 右孩子为空 或者存在右孩子，左孩子为空 那也不属于叶子结点
        // 所以这里会进行判断 如果左节点为空右节点不为空，那就返回右节点深度
        if(node.left == null && node.right!=null){
            return rightDepth + 1;
        }
        if(node.right == null && node.left!=null){
            return leftDepth + 1;
        }
        return 1 + Math.min(leftDepth, rightDepth);
    }
   /*  迭代法
   public int getMinDepth(TreeNode node){
        if (node == null){
            return 0;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        int len = 0;
        while( !queue.isEmpty()){
            len ++;
            int size = queue.size();
            while(size > 0){
                size --;
                TreeNode poll = queue.poll();
                if(poll.left != null){
                    queue.offer(poll.left);
                }
                if(poll.right != null){
                    queue.offer(poll.right);
                }
                // 如果左右节点都为空说明以及到底了，而且又因为是从上到下的层序所以 这一层就是最小深度
                if(poll.left == null && poll.right == null){
                    return len;
                }
            }
        }
        return len;
    }*/

    // 求完全二叉树
    public int countNodes(Node root) {
        if (root == null){
            return 0;
        }
        Deque<Node> queue = new LinkedList<>();
        queue.offer(root);
        int len = 0;
        while( !queue.isEmpty() ){
            int size = queue.size();
            while(size > 0){
                size --;
                Node node = queue.poll();
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
                len ++;
            }
        }
        return len;
    }
    /*   针对完全二叉树性质进行的算法编写
    public int countNodes(TreeNode root) {
          if (root == null){
              return 0;
          }
          // 分别迭代左右子树 然后通过左右子树节点数判断树类型是否为满二叉树
          int leftNums = 0;
          int rightNums = 0;
          TreeNode left = root.left;
          TreeNode right = root.right;
          while(left != null){
              left = left.left;
              leftNums ++;
          }

          while(right != null){
              right = right.right;
              rightNums ++;
          }
          // 如果左子树=右子树 那么这个树就是完全二叉树 通过公式 2^depth -1 得到节点数
          if( rightNums == leftNums){
              return (2<<leftNums)-1;
          }
          return countNodes(root.left) + countNodes(root.right) + 1;
      }
  */

    // 判断是否是平衡二叉树
    public boolean isBalanced(Node root) {
        if(gitHighth(root) == -1){
            return false;
        }else{
            return true;
        }
    }
    // 1.确认递归返回值与传入参数
    int gitHighth(Node node){
        // 2.确认递归结束条件
        if(node == null){
            return 0;
        }
        // 递归单层循环 高度差超过1则返回-1 遇到-1则表示已经不是平衡二叉树
        int rightHigth = gitHighth(node.left);
        if(rightHigth == -1) return -1;
        int leftHigth = gitHighth(node.right);
        if(leftHigth == -1) return -1;

        if(Math.abs(rightHigth - leftHigth) > 1){
            return -1;
        }
        // 返回两边高度最高的作为本节点高度
        return Math.max(rightHigth, leftHigth) + 1;
    }

    // 求二叉树的所有路径
    public List<String> binaryTreePaths(Node root) {
        // 存储结果
        List<String> res = new ArrayList<>();
        // 存储路径
        List<Integer> paths = new ArrayList<>();
        if (root == null){
            return res;
        }
        getPath(root, paths, res);
        return res;
    }
    void getPath(Node node, List paths, List res){
        paths.add(node.e);
        // 如果该节点没有左右孩子,则说明到了叶子结点可以进行一次路径结果添加
        if (node.left == null && node.right == null){
            StringBuilder st = new StringBuilder();
            for(int i = 0; i< paths.size() - 1; i++){
                st.append(paths.get(i));
                st.append("->");
            }
            st.append(paths.get(paths.size() - 1));
            res.add(st.toString());
            return;
        }
        // 如果又忘记了这个回溯过程可以对着一个二叉树试一试
        // 总体来说是每一次函数返回都是一个结果已经添加,那么就需要回溯一次进行其他路径的选择
        if(node.left != null){
            getPath(node.left, paths, res);
            // 回溯
            paths.remove(paths.size() - 1);
        }
        if(node.right != null){
            getPath(node.right, paths, res);
            paths.remove(paths.size() -1);
        }
    }


// 判断完全相同的树
    public boolean isSameTree(Node p, Node q) {
        return compare(p, q);
    }

    public boolean compare(Node p, Node q){
        // 排除多种情况
        if(p == null && q == null){
            return true;
        }
        if(p == null && q!= null){
            return false;
        }
        if (p != null && q == null){
            return false;
        }
        if(p.e != q.e){
            return false;
        }

        boolean leftFlag = compare(p.left, q.left);
        boolean  rightFlag = compare(p.right, q.right);
        return leftFlag && rightFlag;
    }

    // 求所有左叶子节点的和
    // 本题重点是通过左叶子节点的父节点来进行判断
    // 如果一个节点的左节点的左右孩子都为空，那么这个节点的左节点就是叶子结点
    public int sumOfLeftLeaves(Node root) {
        if( root == null){
            return 0;
        }
        int midValue = 0;
        if(root.left != null && root.left.left == null && root.left.right == null){
//            midValue =  root.left.e;
        }

        int leftValue = sumOfLeftLeaves(root.left);
        int rightValue = sumOfLeftLeaves(root.right);

        return leftValue + rightValue + midValue;
    }

    private int Deep = -1;
    private int val = 0;

    public int findBottomLeftValue(Node root) {
        getLeftValue(root, 0);
        return val;
    }
    public void getLeftValue(Node node, int deep){
        // 重点是这里，判断是否是叶子节点，如果是叶子节点就进行深度判断，如果当前深度比记录深度深，那么久进行数值的交换
        // 且因为是从左边开始判断的,所以这里必然是最左边最底层的值
        if (node.left == null && node.right == null){
            if (deep > Deep){
//                val = node.e;
            }
        }
        if( node.left != null){
            deep++;
            getLeftValue(node.left, deep);
            deep--;
        }
        if(node.right != null){
            deep++;
            getLeftValue(node.right, deep);
            deep--;
        }
    }



    // 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
    //
    //来源：力扣（LeetCode）
    //链接：https://leetcode.cn/problems/path-sum
  /*  public boolean hasPathSum(Node root, int targetSum) {
        if (root == null){
            return false;
        }
        // 传入目标之前 先让目标值减去当前节点值
        return traverpath(root, targetSum - root.val);
    }
    public Boolean traverpath(Node node, int count){
        // 判断该节点是否满足条件
        if (node.left == null && node.right == null && count == 0){
            return true;
        }
        // 叶子节点 却没触发上面的count=0，说明不满足条件
        if (node.left == null && node.right == null ){
            return false;
        }
        if (node.left != null){
            // 回溯 传入以及减掉下一点val的值
            if (traverpath(node.left, count-node.left.val)){
                return true;
            }
        }
        if (node.right != null){
            if (traverpath(node.right, count-node.right.val)){
                return true;
            }
        }
        return false;
    }
*/





    // 构建一个私有的添加方法
    // 他的作用是向以node为根的二分搜索树中插入元素E，递归算法


   /*   未改进的方法

     public void add(E e){
        // 1.如果根节点为空，则直接向根节点添加一个元素
        if(root == null){
            root = new Node(e);
            size++;
        }
        else
            add(root, e);
        // 2.如果根节点不为空，
    }

   private void add(Node root, E e){
        // 1.如果插入元素与根节点元素相等，则直接结束
        if(root.e.equals(e)){
            return;
        }
        // 2.如果插入节点小于根节点且根节点左孩子为空，则插入左孩子
        else if(root.e.compareTo(e) > 0 && root.left.e == null){
            root.left = new Node(e);
            size++;
            return;
        }

        // 3.如果插入节点大于根节点且根节点左孩子为空，则插入右孩子
        else if(root.e.compareTo(e) < 0 && root.right.e == null){
            root.right = new Node(e);
            size++;
            return;
        }
        // 4.如果插入节点小于根节点则调用递归放入左孩子根节点地址
        if(root.e.compareTo(e) > 0){
            add(root.left, e);
        }
        // 5.如果插入节点大于根节点则调用递归放入右孩子根节点地址
        else{
            add(root.right, e);
        }
    }*/

/*    这个插入方法是有问题的，因为null其实也可以是我们的一个节点
            所以针对null我们也需要做出把它当做节点的操作
    遇到null我们应该新插入一个Node(新建)   然后返回这个新建节点 并让我们的左右孩子指向它*/






    /*给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
    postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 */


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return null;
    }
  /*  private HashMap<Integer, Integer> inMap;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        inMap = new HashMap<>();
        for(int i=0; i < inorder.length; i++){
            inMap.put(inorder[i], i);
        }
        return build(0, inorder.length - 1, postorder, 0, postorder.length - 1);

    }
    private TreeNode build(int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd){
        // 1.判空
        if (inBegin > inEnd || postBegin > postEnd) {
            return null;
        }
        // 2.根据后序遍历寻找节点在中序的位置
        int rootIndex = inMap.get(postorder[postEnd]);
        // 构造节点
        TreeNode root = new TreeNode(postorder[postEnd]);
        // 3.根据该元素位置切割中序遍历 区分左右区间
        // 保存中序左子树个数，用来确定后序数列的个数
        int lenOfLeft = rootIndex - inBegin;
        // rootIndex rootIndex + 1 抛弃中序遍历中的中结点
        root.left = build(inBegin, rootIndex - 1, postorder, postBegin, postBegin + lenOfLeft - 1);
        root.right = build(rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }*/



    /*给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
    最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)”*/


    // 因为求最小公共祖先，所以需要从低往上遍历
    // 使用后序遍历(先访问左右节点 再访问 父节点判断是否是共同公共祖先)
    // 如果该节点
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /*if(root == p || root == q || root == null){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果左右都找到了就返回 root说明root就是这个祖先节点
        if(left != null && right !=  null){
            return  root;
        }
        // 如果 左子树找到了 qp 或者其中一个 那么就返回left 这里找到了别的 地方就没有 所以按照逻辑依次网上传都是这个left节点
        else if(left != null && right == null){
            return left;
        }
        else if(left == null && right != null){
            return right;
        }
        else return null;*/
        return null;
    }
}








